package Offer;

/**
 * 数值的整数次方
 *
 * @author 是阿秋啊
 * @date 2022/04/18 20:31
 **/
public class Num16 {
    // 迭代
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }
        // 之所以用long代替是因为当n = -2^31时需要变为正超过int
        long b = n;
        double ret = 1.0;
        if (b < 0) {
            b = -b;
            x = 1 / x;
        }
        // 主要思想
        // 将3^10 = 3*3*3*3*3*3*3*3*3*3
        // 变成 = 9^5 = 9*9*9*9*9
        // 指数为奇数的时候 = 9*9^4 = 9*81^2
        while (b > 0) {
            if ((b & 1) == 1) {
                // 当进制为奇数的时候，需要单独乘一次
                ret *= x;
            }
            x *= x;
            b >>= 1;
        }
        return ret;
    }
    // 递归
    public static double myPow1(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public static double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        // 相比于迭代，迭代是自顶向下分解
        // 递归是先进入到最底端自底向上合成
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    public static void main(String[] args) {
        System.out.println(myPow1(3,10));
    }
}
